#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<fstream>
#include<sstream>
#include<map>
#include<string>
#include<ctime>
#include<unordered_map>
using namespace std;

//string node_file = "matchdata/performance0.4/node.csv";
//string link_file = "matchdata/performance0.4/link.csv";
//string traffic_file = "matchdata/performance0.4/traffic.csv";
//string new_node_file = "matchdata/performance0.4/new_node.csv";
//string new_link_file = "matchdata/performance0.4/new_link.csv";
//string path_file = "matchdata/performance0.4/path.csv";
//string path_file = "matchdata/performance0.2/path.csv";
//string node_file = "matchdata/performance0.2/node.csv";
//string link_file = "matchdata/performance0.2/link.csv";
//string traffic_file = "matchdata/performance0.2/traffic.csv";
//string new_node_file = "matchdata/performance0.2/new_node.csv";
//string new_link_file = "matchdata/performance0.2/new_link.csv";
//string path_file = "matchdata/performance0.15/path.csv";
//string node_file = "matchdata/performance0.15/node.csv";
//string link_file = "matchdata/performance0.15/link.csv";
//string traffic_file = "matchdata/performance0.15/traffic.csv";
//string new_node_file = "matchdata/performance0.15/new_node.csv";
//string new_link_file = "matchdata/performance0.15/new_link.csv";
string node_file = "matchdata/performance0.45/node.csv";
string link_file = "matchdata/performance0.45/link.csv";
string traffic_file = "matchdata/performance0.45/traffic.csv";
string new_node_file = "matchdata/performance0.45/new_node.csv";
string new_link_file = "matchdata/performance0.45/new_link.csv";
string path_file = "matchdata/performance0.45/path.csv";
//string node_file = "matchdata/function/node.csv";
//string link_file = "matchdata/function/link.csv";
//string traffic_file = "matchdata/function/traffic.csv";
//string new_node_file = "matchdata/function/new_node.csv";
//string new_link_file = "matchdata/function/new_link.csv";
//string path_file = "matchdata/function/path.csv";
vector<string> split(const string& str, const string& delim) {
    vector<string> res;
    if("" == str) return res;
    char * strs = new char[str.length() + 1];
    strcpy(strs, str.c_str());
    char * d = new char[delim.length() + 1];
    strcpy(d, delim.c_str());
    char *p = strtok(strs, d);
    while(p) {
        string s = p;
        res.push_back(s);
        p = strtok(NULL, d);
    }
    return res;
}
struct Node{
    string node_id;
    int node_type;
    string node_type_str;
    int interface_capacity;
    int interface_used;
    int node_idx;
};
struct Link{
    string link_id, start_node_id, end_node_id;
    int start_node_idx, end_node_idx;
    double capacity;
    double flow;
    string rev_link_id;
    int link_idx;
    int rev_link_idx;
};
struct Traffic{
    string traffic_id, from_node_id, to_node_id;
    int from_node_idx, to_node_idx;
    double flow;
    int tag;
};
unordered_map<string, int> node_type_mp;
unordered_map<string, Node> node_mp;
unordered_map<string, Link> link_mp;
unordered_map<string, vector<string>> node_link_mp;
vector<Traffic> traffic_vec;
int node_num = 0, link_num = 0;
// node_id列表，link_id列表，邻接矩阵
string node_arr[1300], link_arr[3000];
int f[1300][1300];
int c[4] = {1, 2, 3};
int d[4] = {1, 10, 100};
// 接边类型
int e[5][5] = {{2, 2, 1, 1, 1},
               {2, 0, 0, 0, 1},
               {1, 0, 0, 0, 1},
               {1, 0, 0, 0, 0},
               {1, 1, 1, 0, 0}};
// 加管道类型 0: 1/10  1: 10  2: 10/100 -1:无
int g[5][5] = {{0, 0, -1, -1, -1},
               {0, 0, 1, 1, -1},
               {-1, 1, 1, 1, -1},
               {-1, 1, 1, 2, 2},
               {-1, -1, -1, 2, 2}};
double link_coe = 0.4, total_coe = 0.3;
// 求解辅助数组
int q[1300], head, tail, visited[1300];
int last_link[1300][1300];
struct Input_T{
    int n;
    vector<vector<int>> graph;
    vector<Link> link;
    vector<Traffic> traffic;
};
struct Output_T{
    int is_allocated;
    vector<int> status;
    vector<vector<string>> sol;
    vector<string> traffic_id;
    vector<double> add_pip_flow;
};
struct Add_T{
    vector<Link> link;
};
Add_T final_add_t;
struct Data_T{
    vector<vector<int>> dis;
    double rate;
};
struct Node_T{
    string node_id;
    int node_type;
    int du;
    int interface_capacity;
    int interface_used;
    int old_idx;
    int is_used;
    int dis;
};
bool cmp2(Node_T a, Node_T b){
    if (a.node_type == 0 && b.node_type != 0) return true;
    if (a.node_type != 0 && b.node_type == 0) return false;
    if (a.node_type == 4 && b.node_type != 4) return true;
    if (a.node_type != 4 && b.node_type == 4) return false;
//    return a.du < b.du;
    if (a.node_type == 0){
        if (a.interface_used == b.interface_used) return a.dis < b.dis;
        return a.interface_used < b.interface_used;
    }
    return a.interface_capacity - a.interface_used < b.interface_capacity - b.interface_used;
}
bool cmp1(Traffic a, Traffic b){
    return a.flow > b.flow;
}
void init(){
    node_type_mp["核心层"] = 4;
    node_type_mp["核心-汇聚层"] = 3;
    node_type_mp["汇聚层"] = 2;
    node_type_mp["汇聚-接入层"] = 1;
    node_type_mp["汇聚接入层"] = 1;
    node_type_mp["接入层"] = 0;
    ifstream file;
    file.open(node_file, ios_base::in);
    string s;
    memset(f, 0, sizeof(f));
    node_num = 0;
    while (getline(file, s)){
        node_num += 1;
        if (node_num == 1) continue;
        vector<string> tmp = split(s, ",");
        Node node;
        node.node_id = tmp[0];
        node.node_type = node_type_mp[tmp[1]];
        node.node_type_str = tmp[1];
        node.interface_capacity = stoi(tmp[2]);
        node.interface_used = 0;
        node.node_idx = node_num - 1;
        node_mp[node.node_id] = node;
        node_arr[node_num - 1] = node.node_id;
        vector<string> link_vec;
        node_link_mp[node.node_id] = link_vec;
    }
//    for (int i = 0; i < 10; i++){
//        node_num += 1;
//        Node node;
//        node.node_id = "new_" + to_string(i);
//        node.node_type = 2;
//        node.node_type_str = "汇聚层";
//        node.interface_capacity = 10;
//        node.interface_used = 0;
//        node.node_idx = node_num - 1;
//        node_mp[node.node_id] = node;
//        node_arr[node_num - 1] = node.node_id;
//        vector<string> link_vec;
//        node_link_mp[node.node_id] = link_vec;
//    }
    file.close();
    file.open(link_file, ios_base::in);
    link_num = 0;
    while (getline(file, s)){
        link_num += 1;
        if (link_num == 1) continue;
        vector<string> tmp = split(s, ",");
        Link link, link_rev;
        link.link_id = tmp[0];
        link.start_node_id = tmp[1];
        link.end_node_id = tmp[2];
        link.start_node_idx = node_mp[tmp[1]].node_idx;
        link.end_node_idx = node_mp[tmp[2]].node_idx;
        link.capacity = stod(tmp[3]);
        link.flow = 0;
        link.link_idx = link_num - 1;
        link_arr[link_num - 1] = link.link_id;
        link_num += 1;
        link_rev.link_id = tmp[0] + "_rev";
        link_rev.start_node_id = tmp[2];
        link_rev.end_node_id = tmp[1];
        link_rev.start_node_idx = node_mp[tmp[2]].node_idx;
        link_rev.end_node_idx = node_mp[tmp[1]].node_idx;
        link_rev.capacity = stod(tmp[3]);
        link_rev.flow = 0;
        link_rev.link_idx = link_num - 1;
        link.rev_link_id = link_rev.link_id;
        link_rev.rev_link_id = link.link_id;
        link.rev_link_idx = link_num - 1;
        link_rev.rev_link_idx = link_num - 2;
        link_arr[link_num - 1] = link_rev.link_id;
        f[node_mp[link.start_node_id].node_idx][node_mp[link.end_node_id].node_idx] = 1;
        f[node_mp[link.end_node_id].node_idx][node_mp[link.start_node_id].node_idx] = 1;
        link_mp[link.link_id] = link;
        link_mp[link_rev.link_id] = link_rev;
        node_link_mp[link.start_node_id].push_back(link.link_id);
        node_link_mp[link_rev.start_node_id].push_back(link_rev.link_id);
    }
    file.close();
    file.open(traffic_file, ios_base::in);
    int cnt = 0;
    while (getline(file, s)){
        cnt += 1;
        if (cnt == 1) continue;
        vector<string> tmp = split(s, ",");
        Traffic traffic;
        traffic.traffic_id = tmp[0];
        traffic.from_node_id = tmp[1];
        traffic.to_node_id = tmp[2];
        traffic.flow = stod(tmp[3]);
        traffic.from_node_idx = node_mp[tmp[1]].node_idx;
        traffic.to_node_idx = node_mp[tmp[2]].node_idx;
        traffic_vec.push_back(traffic);
    }
    sort(traffic_vec.begin(), traffic_vec.end(), cmp1);
//    for (int i = 0; i < traffic_vec.size(); i++){
//        cout << traffic_vec[i].flow << endl;
//    }
    file.close();
}
void show_data(){
    cout << node_num << " " << link_num << endl;
    cout << "node_mp" << endl;
    for (auto x:node_mp){
        cout << x.first << " " << x.second.node_type_str << " " << x.second.interface_capacity << " ";
        cout << x.second.node_idx << endl;
    }
    cout << "link_mp" << endl;
    for (auto x:link_mp){
        cout << x.first << " " << x.second.start_node_id << " " << x.second.end_node_id << " ";
        cout << x.second.capacity << " " << x.second.flow << " " << x.second.rev_link_id << endl;
    }
    cout << "node_link_mp" << endl;
    for (auto x:node_link_mp){
        if (x.second.size() > 0){
            cout << x.first << " " << x.second[0] << endl;
        }
    }
    cout << "traffic_vec" << endl;
    for (int i = 0; i < traffic_vec.size(); i++){
        cout << traffic_vec[i].traffic_id << " " << traffic_vec[i].from_node_id << " ";
        cout << traffic_vec[i].to_node_id << " " << traffic_vec[i].flow << endl;
    }
}
void analyse_data(){
    cout << node_num << " " << link_num << endl;
    cout << "node_mp" << endl;
    double total_capacity = 0;
    for (auto x:node_mp){
        total_capacity += x.second.interface_capacity;
    }
    cout << total_capacity * 1.0 / node_num << endl;
    map<string, double> flow_from_mp, flow_to_mp;
    for (int i = 0; i < traffic_vec.size(); i++){
        string from_node_id = traffic_vec[i].from_node_id;
        string to_node_id = traffic_vec[i].to_node_id;
        double flow = traffic_vec[i].flow;
        if (flow_from_mp.count(from_node_id) == 0){
            flow_from_mp[from_node_id] = 0;
        }
        flow_from_mp[from_node_id] += flow;
        if (flow_to_mp.count(to_node_id) == 0){
            flow_to_mp[to_node_id] = 0;
        }
        flow_to_mp[to_node_id] += flow;
    }
    for (auto x:flow_from_mp){
        cout << x.first << " " << x.second << " " << flow_to_mp[x.first] << endl;
    }
}
Input_T prepare_data(){
    Input_T output;
    output.n = node_num - 1;
    output.graph.clear();
    vector<int> tmp;
    output.graph.push_back(tmp);
    for (int i = 1; i <= output.n; i++){
        vector<int> tmp;
        int sz = node_link_mp[node_arr[i]].size();
        for (int j = 0; j < sz; j++){
            tmp.push_back(link_mp[node_link_mp[node_arr[i]][j]].link_idx);
        }
        output.graph.push_back(tmp);
    }
    Link link;
    output.link.clear();
    output.link.push_back(link);
    for (int i = 1; i < link_num; i++){
        output.link.push_back(link_mp[link_arr[i]]);
        output.link[i].flow = 0;
    }
    output.traffic = traffic_vec;
    for (int i = 0; i < output.traffic.size(); i++){
        output.traffic[i].tag = 0;
    }
    return output;
};
Output_T planning(Input_T input_T){
    int last_cnt = -1, pos = -1, flag;
    Output_T output;
    output.status.clear();
    output.sol.clear();
    output.traffic_id.clear();
    for (int i = 0; i < input_T.traffic.size(); i++){
        output.status.push_back(0);
        output.traffic_id.push_back(input_T.traffic[i].traffic_id);
        vector<string> tmp;
        output.sol.push_back(tmp);
    }
    for (int i = 1; i < input_T.link.size(); i++){
        if (input_T.link[i].flow > 0){
            cout << input_T.link[i].link_id << " " << input_T.link[i].flow << endl;
        }
        input_T.link[i].flow = 0;
    }
    while (true){
        flag = 0;
        memset(last_link, 0, sizeof(last_link));
        for (int i = 1; i <= input_T.n; i++){
            memset(visited, 0, sizeof(visited));
            head = 1;
            tail = 1;
            q[1] = i;
            visited[i] = 1;
            while (tail <= head){
                int now_idx = q[tail];
                int sz = input_T.graph[now_idx].size();
                for (int j = 0; j < sz; j++){
                    int lidx = input_T.graph[now_idx][j];
                    int x = input_T.link[lidx].end_node_idx;
                    if (visited[x] == 0 && (input_T.link[lidx].flow + input_T.traffic[pos].flow)
                        / input_T.link[lidx].capacity < link_coe){
                        head += 1;
                        visited[x] = 1;
                        q[head] = x;
                        last_link[i][x] = lidx;
                    }
                }
                tail += 1;
            }
        }
//        for (int i = 1; i <= input_T.n; i++){
//            for (int j = 1; j <= input_T.n; j++) cout << last_link[i][j] << " ";
//            cout << endl;
//        }
        int cnt = 0;
        for (int i = 0; i < input_T.traffic.size(); i++){
            if (input_T.traffic[i].tag == 1) continue;
            int from_node_idx = input_T.traffic[i].from_node_idx;
            int to_node_idx = input_T.traffic[i].to_node_idx;
            double flow = input_T.traffic[i].flow;
            int now = to_node_idx;
            int flag = 1;
            while (now != from_node_idx){
                int lidx = last_link[from_node_idx][now];
                if (lidx == 0 || input_T.link[lidx].flow + flow >= input_T.link[lidx].capacity * link_coe){
                    flag = 0;
                    break;
                }
                now = input_T.link[lidx].start_node_idx;
            }
            if (flag == 0){
//                cout << "fail to allocated: " << " " << input_T.traffic[i].traffic_id << " ";
//                cout << from_node_idx << " " << to_node_idx << " " << flow << endl;
                if (flag == 0) pos = i;
                flag = 1;
                cnt += 1;
            }else{
                input_T.traffic[i].tag = 1;
                output.status[i] = 1;
                vector<string> tmp;
                now = to_node_idx;
                while (now != from_node_idx){
                    int lidx = last_link[from_node_idx][now];
                    input_T.link[lidx].flow += flow;
                    tmp.push_back(input_T.link[lidx].link_id);
                    input_T.link[input_T.link[lidx].rev_link_idx].flow += flow;
                    now = input_T.link[lidx].start_node_idx;
                }
                for (int j = tmp.size() - 1;j >= 0; j--){
                    output.sol[i].push_back(tmp[j]);
                }
            }
        }
        cout << "fail cnt: " << cnt << endl;
//        for (int i = 1; i < input_T.link.size(); i++){
//            cout << input_T.link[i].start_node_id << " " << input_T.link[i].end_node_id << " ";
//            cout << input_T.link[i].capacity << " " << input_T.link[i].flow << endl;
//        }
        if (cnt == 0) break;
        if (last_cnt == cnt) {
            link_coe += 0.1;
            cout << "update coe to: " << link_coe << endl;
//            break;
        }
        last_cnt = cnt;
    }
    if (last_cnt == 0){
        output.is_allocated = 1;
    }else{
        output.is_allocated = 0;
    }
    output.add_pip_flow.clear();
    for (int i = link_num; i < input_T.link.size(); i++){
        output.add_pip_flow.push_back(input_T.link[i].flow);
    }
    double pipe_capacity = 0, pipe_flow = 0, util = 0;
    for (int i = 1; i < input_T.link.size(); i++){
        if (input_T.link[i].flow / input_T.link[i].capacity > util){
            util = input_T.link[i].flow / input_T.link[i].capacity;
        }
        pipe_capacity += input_T.link[i].capacity;
        pipe_flow += input_T.link[i].flow;
    }
    cout << "pipe util: " << util << endl;
    cout << "total util: " << pipe_flow / pipe_capacity << endl;
    return output;
};
Output_T planning2(Input_T input_T){
    int last_cnt = -1, pos = -1, flag;
    Output_T output;
    output.status.clear();
    output.sol.clear();
    output.traffic_id.clear();
    for (int i = 0; i < input_T.traffic.size(); i++){
        output.status.push_back(0);
        output.traffic_id.push_back(input_T.traffic[i].traffic_id);
        vector<string> tmp;
        output.sol.push_back(tmp);
    }
    for (int i = 0; i < input_T.link.size(); i++){
        input_T.link[i].flow = 0;
    }
    while (true){
        flag = 0;
        memset(last_link, 0, sizeof(last_link));
        for (int i = 1; i <= input_T.n; i++){
            memset(visited, 0, sizeof(visited));
            head = 1;
            tail = 1;
            q[1] = i;
            visited[i] = 1;
            while (tail <= head){
                int now_idx = q[tail];
                int sz = input_T.graph[now_idx].size();
                for (int j = 0; j < sz; j++){
                    int lidx = input_T.graph[now_idx][j];
                    int x = input_T.link[lidx].end_node_idx;
                    if (visited[x] == 0 && (input_T.link[lidx].flow + input_T.traffic[pos].flow)
                        / input_T.link[lidx].capacity < link_coe){
                        head += 1;
                        visited[x] = 1;
                        q[head] = x;
                        last_link[i][x] = lidx;
                    }
                }
                tail += 1;
            }
        }
//        for (int i = 1; i <= input_T.n; i++){
//            for (int j = 1; j <= input_T.n; j++) cout << last_link[i][j] << " ";
//            cout << endl;
//        }
        int cnt = 0;
        for (int i = 0; i < input_T.traffic.size(); i++){
            if (input_T.traffic[i].tag == 1) continue;
            int from_node_idx = input_T.traffic[i].from_node_idx;
            int to_node_idx = input_T.traffic[i].to_node_idx;
            double flow = input_T.traffic[i].flow;
            int now = to_node_idx;
            int flag = 1;
            while (now != from_node_idx){
                int lidx = last_link[from_node_idx][now];
                if (lidx == 0 || input_T.link[lidx].flow + flow >= input_T.link[lidx].capacity * link_coe){
                    flag = 0;
                    break;
                }
                now = input_T.link[lidx].start_node_idx;
            }
            if (flag == 0){
//                cout << "fail to allocated: " << " " << input_T.traffic[i].traffic_id << " ";
//                cout << from_node_idx << " " << to_node_idx << " " << flow << endl;
                if (flag == 0) pos = i;
                flag = 1;
                cnt += 1;
            }else{
                input_T.traffic[i].tag = 1;
                output.status[i] = 1;
                vector<string> tmp;
                now = to_node_idx;
                while (now != from_node_idx){
                    int lidx = last_link[from_node_idx][now];
                    input_T.link[lidx].flow += flow;
                    tmp.push_back(input_T.link[lidx].link_id);
                    input_T.link[input_T.link[lidx].rev_link_idx].flow += flow;
                    now = input_T.link[lidx].start_node_idx;
                }
                for (int j = tmp.size() - 1;j >= 0; j--){
                    output.sol[i].push_back(tmp[j]);
                }
            }
        }
        cout << "fail cnt: " << cnt << endl;
//        for (int i = 1; i < input_T.link.size(); i++){
//            cout << input_T.link[i].start_node_id << " " << input_T.link[i].end_node_id << " ";
//            cout << input_T.link[i].capacity << " " << input_T.link[i].flow << endl;
//        }
        if (last_cnt == cnt) {
            break;
        }
        last_cnt = cnt;
        if (cnt == 0) break;
    }
    if (last_cnt == 0){
        output.is_allocated = 1;
    }else{
        output.is_allocated = 0;
    }
    output.add_pip_flow.clear();
    for (int i = link_num; i < input_T.link.size(); i++){
        output.add_pip_flow.push_back(input_T.link[i].flow);
    }
    double pipe_capacity = 0, pipe_flow = 0, util = 0;
    for (int i = 1; i < input_T.link.size(); i++){
        if (input_T.link[i].flow / input_T.link[i].capacity > util){
            util = input_T.link[i].flow / input_T.link[i].capacity;
        }
        pipe_capacity += input_T.link[i].capacity;
        pipe_flow += input_T.link[i].flow;
    }
    cout << "pipe util: " << util << endl;
    cout << "total util: " << pipe_flow / pipe_capacity << endl;
    cout << pipe_flow << " " << pipe_capacity << endl;
    if (pipe_flow / pipe_capacity >= 0.3){
        output.is_allocated = 0;
    }
    return output;
};
Input_T combine(Add_T add_t, Input_T input_t){
    Input_T output = input_t;
    int m = output.link.size();
    cout << "combine: " << m << " " << add_t.link.size() << endl;
    for (int i = 0; i < add_t.link.size(); i++){
        int start_node_idx = add_t.link[i].start_node_idx;
        output.link.push_back(add_t.link[i]);
        output.link[m + i].link_idx = m + i;
        if (i % 2 == 0){
            output.link[m + i].rev_link_idx = m + i + 1;
        }else{
            output.link[m + i].rev_link_idx = m + i - 1;
        }
        output.graph[start_node_idx].push_back(m + i);
    }
    return output;
}
vector<vector<int>> calc_dis(Input_T input_T){
    vector<vector<int>> dis;
    for (int i = 0; i <= input_T.n; i++){
        vector<int> tmp;
        for (int j = 0; j <= input_T.n; j++){
            tmp.push_back(-1);
        }
        dis.push_back(tmp);
    }
    for (int i = 1; i <= input_T.n; i++){
        memset(visited, 0, sizeof(visited));
        head = 1;
        tail = 1;
        q[1] = i;
        dis[i][i] = 0;
        visited[i] = 1;
        while (tail <= head){
            int now_idx = q[tail];
            int sz = input_T.graph[now_idx].size();
            for (int j = 0; j < sz; j++){
                int lidx = input_T.graph[now_idx][j];
                int x = input_T.link[lidx].end_node_idx;
                if (visited[x] == 0){
                    head += 1;
                    visited[x] = 1;
                    q[head] = x;
                    dis[i][x] = dis[i][now_idx] + 1;
                }
            }
            tail += 1;
        }
    }
    return dis;
}
Data_T calc_rate(Input_T input_T){
    vector<vector<int>> dis;
    for (int i = 0; i <= input_T.n; i++){
        vector<int> tmp;
        for (int j = 0; j <= input_T.n; j++){
            tmp.push_back(-1);
        }
        dis.push_back(tmp);
    }
    for (int i = 1; i <= input_T.n; i++){
        memset(visited, 0, sizeof(visited));
        head = 1;
        tail = 1;
        q[1] = i;
        dis[i][i] = 0;
        visited[i] = 1;
        while (tail <= head){
            int now_idx = q[tail];
            int sz = input_T.graph[now_idx].size();
            for (int j = 0; j < sz; j++){
                int lidx = input_T.graph[now_idx][j];
                int x = input_T.link[lidx].end_node_idx;
                if (visited[x] == 0){
                    head += 1;
                    visited[x] = 1;
                    q[head] = x;
                    dis[i][x] = dis[i][now_idx] + 1;
                }
            }
            tail += 1;
        }
    }
    double total = 0, flow = 0;
    for (int i = 1; i <= input_T.link.size(); i++){
        total += input_T.link[i].capacity;
    }
    for (int i = 0; i < input_T.traffic.size(); i++){
        flow += dis[input_T.traffic[i].from_node_idx][input_T.traffic[i].to_node_idx] * input_T.traffic[i].flow;
    }
    total /= 2;
    Data_T data_t;
    data_t.dis = dis;
    data_t.rate = flow / total;
    return data_t;
}
Add_T add_extra_graph(){
    vector<Node_T> node_vec;
    for (int i = 1; i < node_num; i++){
        Node_T node_t;
        Node node = node_mp[node_arr[i]];
        node_t.node_id = node.node_id;
        node_t.node_type = node.node_type;
        node_t.interface_capacity = node.interface_capacity;
        node_t.interface_used = 0;
        node_t.du = 0;
        node_t.dis = -1;
        node_t.is_used = 0;
        node_t.old_idx = node.node_idx;
        node_vec.push_back(node_t);
    }
    for (int i = 1; i < link_num; i++){
        Link link = link_mp[link_arr[i]];
        node_vec[link.start_node_idx - 1].du += 1;
        node_vec[link.end_node_idx - 1].du += 1;
    }
    int du[1005];
    memset(du, 0, sizeof(du));
    for (int i = 0; i < node_vec.size(); i++){
        du[node_vec[i].du / 2] += 1;
    }
    head = 0;
    for (int i = 0; i < node_vec.size(); i++){
        if (node_vec[i].node_type == 1){
            head += 1;
            q[head] = i;
            node_vec[i].dis = 0;
        }
    }
    tail = 1;
    while (tail <= head){
        int i = q[tail];
        for (int j = 0; j < node_vec.size(); j++){
            if (node_vec[j].node_type == 0 && node_vec[j].dis == -1 &&
                f[node_vec[i].old_idx][node_vec[j].old_idx] == 1){
                node_vec[j].dis = node_vec[i].dis + 1;
                head += 1;
                q[head] = j;
            }
        }
        tail += 1;
    }
//    for (int i = 0; i < node_vec.size(); i++)
//        cout << node_vec[i].node_id << " " << node_vec[i].node_type << " " << node_vec[i].dis << endl;
    Add_T output;
    output.link.clear();
    int cnt = 0, pos = 0, end_pos, link_type;
    vector<vector<int>> dis = calc_dis(prepare_data());
    while (pos != -1){
        sort(node_vec.begin(), node_vec.end(), cmp2);
//        for (int i = 0; i < node_vec.size(); i++){
//            cout << node_vec[i].node_id << " " << node_vec[i].node_type << " ";
//            cout << node_vec[i].interface_capacity << " " << node_vec[i].interface_used << endl;
//        }
        cnt += 1;
//        if (cnt % 10 == 0){
//            Data_T data_t = calc_rate(combine(output, prepare_data()));
//            cout << "data_t.rate: " << data_t.rate << endl;
//            if (data_t.rate < 0.3) break;
//            dis = data_t.dis;
//        }
        pos = -1;
        for (int i = 0; i < node_vec.size(); i++){
            if (node_vec[i].is_used == 0 && node_vec[i].interface_used < node_vec[i].interface_capacity){
                end_pos = -1;
                int tmp_dis = 0, tmp_du = 0, tmp_left = 0, tmp_lx = 500;
                for (int j = 0; j < node_vec.size(); j++){
                    if (i != j && node_vec[j].is_used == 0 &&
                        node_vec[j].interface_used < node_vec[j].interface_capacity &&
                        (e[node_vec[j].node_type][node_vec[i].node_type] == 0 ||
                            (e[node_vec[j].node_type][node_vec[i].node_type] == 2 &&
                                f[node_vec[i].old_idx][node_vec[j].old_idx] == 1))){

//                        if (dis[node_vec[i].old_idx][node_vec[j].old_idx] > tmp_dis ||
//                            (dis[node_vec[i].old_idx][node_vec[j].old_idx] == tmp_dis &&
//                                node_vec[j].du > tmp_du)){
//                            tmp_dis = dis[node_vec[i].old_idx][node_vec[j].old_idx];
//                            end_pos = j;
//                            tmp_du = node_vec[j].du;
//                            link_type = e[node_vec[j].node_type][node_vec[i].node_type];
//                        }
                        if (node_vec[i].node_type != 0){
                            if (node_vec[j].interface_capacity - node_vec[j].interface_used > tmp_left){
                                end_pos = j;
                                tmp_left = node_vec[j].interface_capacity - node_vec[j].interface_used;
                                link_type = g[node_vec[j].node_type][node_vec[i].node_type];
                            }
                        }else{
                            if (node_vec[j].dis < tmp_lx){
                                tmp_lx = node_vec[j].dis;
                                end_pos = j;
                                link_type = 0;
                            }
                        }
                    }
                }
                if (end_pos != -1){
                    pos = i;
                    break;
                }else{
                    node_vec[i].is_used = 1;
                }
            }
        }
        if (pos != -1){
            int end_idx = node_vec[end_pos].old_idx;
            int start_idx = node_vec[pos].old_idx;
            Link link, link_rev;
            link.link_id = "new_" + to_string(output.link.size());
            link.start_node_id = node_arr[start_idx];
            link.end_node_id = node_arr[end_idx];
            link.start_node_idx = start_idx;
            link.end_node_idx = end_idx;
            // todo
//            if (link_type == 0 || link_type == 1){
//                link.capacity = 10;
//            }else{
//                link.capacity = 100;
//            }
            link.capacity = 10;
            link.flow = 0;
            link.rev_link_id = "new_" + to_string(output.link.size()) + "_rev";

            link_rev.link_id = "new_" + to_string(output.link.size()) + "_rev";
            link_rev.start_node_id = node_arr[end_idx];
            link_rev.end_node_id = node_arr[start_idx];
            link_rev.start_node_idx = end_idx;
            link_rev.end_node_idx = start_idx;
            link_rev.capacity = link.capacity;
            link_rev.flow = 0;
            link_rev.rev_link_id = "new_" + to_string(output.link.size());
            output.link.push_back(link);
            output.link.push_back(link_rev);

            node_vec[pos].interface_used += 1;
            node_vec[pos].du += 2;
            node_vec[end_pos].interface_used += 1;
            node_vec[end_pos].du += 2;
        }
    }
//    for (int i = 0; i < node_vec.size(); i++){
//        cout << node_vec[i].node_id << " " << node_vec[i].du << " " << node_vec[i].interface_used << endl;
//    }
    return output;
};
void print_to_file(Output_T output_t, Add_T add_t){
    ofstream file;
    file.open(new_node_file);
    file << "节点id,所属域,剩余端口数" << endl;
    file.close();
    file.open(new_link_file);
    file << "链路id,起点,终点,带宽" << endl;
    for (int i = 0; i < add_t.link.size(); i++){
        if (i % 2 == 0){
            file << add_t.link[i].link_id << "," << add_t.link[i].start_node_id << ",";
            file << add_t.link[i].end_node_id << "," << add_t.link[i].capacity << endl;
        }
    }
    file.close();
    file.open(path_file);
    file << "流量id,路径" << endl;
    for (int i = 0; i < output_t.sol.size(); i++){
        file << output_t.traffic_id[i] << ",";
        for (int j = 0; j < output_t.sol[i].size(); j++){
            if (j == 0){
                file << output_t.sol[i][j];
            }else{
                file << "-->" << output_t.sol[i][j];
            }
        }
        file << endl;
    }
    file.close();
}
void show_status(){
    int cnt = 0;
    for (auto x:link_mp){
//        cout << x.first << " " << x.second.start_node_id << " " << x.second.end_node_id << " ";
//        cout << x.second.capacity << " " << x.second.flow << " " << endl;
        if (x.second.flow / x.second.capacity < 0.1){
            cnt += 1;
        }
    }
    cout << "empty pip: " << cnt << endl;
};
void try_decline(Add_T add_t, Output_T output_t, double line){
    Add_T now_add_t;
    Output_T output;
    now_add_t.link.clear();
    int pos = 0;
    while (pos < add_t.link.size()){
        if (output_t.add_pip_flow[pos] + output_t.add_pip_flow[pos + 1] > line){
            now_add_t.link.push_back(add_t.link[pos]);
            now_add_t.link[now_add_t.link.size() - 1].flow = output_t.add_pip_flow[pos];
            now_add_t.link.push_back(add_t.link[pos + 1]);
            now_add_t.link[now_add_t.link.size() - 1].flow = output_t.add_pip_flow[pos + 1];
        }
        pos += 2;
    }
//    output = planning2(combine(now_add_t, prepare_data()));
//    cout << "decline success: " << output.is_allocated << endl;
//    if (output.is_allocated == 0){
//        return output_t;
//    }
    final_add_t = now_add_t;
}
int main(){
    init();
//    show_data();
//    analyse_data();
    double begin = (double)clock() / CLOCKS_PER_SEC;
    Add_T add_t = add_extra_graph(), final_add_t2, final_add_t3, final_add_t4;
    Add_T final_add_t5, final_add_t6, final_add_t7, final_add_t8;
    Add_T final_add_t9, final_add_t10;
    final_add_t = add_t;
    Output_T output_t = planning(combine(add_t, prepare_data()));
//    show_status();
    try_decline(add_t, output_t, 0);
    final_add_t2 = final_add_t;
    Output_T new_output_t2 = planning2(combine(final_add_t2, prepare_data()));
    try_decline(add_t, output_t, 0.25);
    final_add_t3 = final_add_t;
    Output_T new_output_t3 = planning2(combine(final_add_t3, prepare_data()));
    try_decline(add_t, output_t, 0.5);
    final_add_t4 = final_add_t;
    Output_T new_output_t4 = planning2(combine(final_add_t4, prepare_data()));
    try_decline(add_t, output_t, 0.75);
    final_add_t5 = final_add_t;
    Output_T new_output_t5 = planning2(combine(final_add_t5, prepare_data()));
    try_decline(add_t, output_t, 1);
    final_add_t6 = final_add_t;
    Output_T new_output_t6 = planning2(combine(final_add_t6, prepare_data()));
    try_decline(add_t, output_t, 1.25);
    final_add_t7 = final_add_t;
    Output_T new_output_t7 = planning2(combine(final_add_t7, prepare_data()));
    try_decline(add_t, output_t, 1.5);
    final_add_t8 = final_add_t;
    Output_T new_output_t8 = planning2(combine(final_add_t8, prepare_data()));
    try_decline(add_t, output_t, 1.75);
    final_add_t9 = final_add_t;
    Output_T new_output_t9 = planning2(combine(final_add_t9, prepare_data()));
    try_decline(add_t, output_t, 2);
    final_add_t10 = final_add_t;
    Output_T new_output_t10 = planning2(combine(final_add_t10, prepare_data()));
    if (new_output_t10.is_allocated == 1){
        print_to_file(new_output_t10, final_add_t10);
    }else if (new_output_t9.is_allocated == 1){
        cout << "十次规划失败" << endl;
        print_to_file(new_output_t9, final_add_t9);
    }else if (new_output_t8.is_allocated == 1){
        cout << "九次规划失败" << endl;
        print_to_file(new_output_t8, final_add_t8);
    }else if (new_output_t7.is_allocated == 1){
        cout << "八次规划失败" << endl;
        print_to_file(new_output_t7, final_add_t7);
    }else if (new_output_t6.is_allocated == 1){
        cout << "七次规划失败" << endl;
        print_to_file(new_output_t6, final_add_t6);
    }else if (new_output_t5.is_allocated == 1){
        cout << "六次规划失败" << endl;
        print_to_file(new_output_t5, final_add_t5);
    }else if (new_output_t4.is_allocated == 1){
        cout << "五次规划失败" << endl;
        print_to_file(new_output_t4, final_add_t4);
    }else if (new_output_t3.is_allocated == 1){
        cout << "四次规划失败" << endl;
        print_to_file(new_output_t3, final_add_t3);
    }else if (new_output_t2.is_allocated == 1){
        cout << "三次规划失败" << endl;
        print_to_file(new_output_t2, final_add_t2);
    }else{
        cout << "二次规划失败" << endl;
        print_to_file(output_t, add_t);
    }
    double end = (double)clock() / CLOCKS_PER_SEC;
    cout << "running time: " << end - begin << "s" << endl;
}
